package binarytree;

import javax.security.auth.callback.CallbackHandler;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class binaryTree {

    //树的每一个节点都包含数值域和左右孩子结点的引用
    public static class TreeNode{
        char val;
        TreeNode left;
        TreeNode right;

        public TreeNode(char val) {
            this.val = val;
        }
    }

    //定义树的头节点
    public TreeNode root;

    //创建一棵二叉树
    public void createTree() {
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');

        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        E.right = H;
        root=A;
    }

    ///////重点基本方法////////





    // 前序遍历(根->左->右)
    public void preOrder(TreeNode root){
        //判断当前根节点或子树头节点是否为空
        if(root==null)return;
        //先打印根
        System.out.print(root.val+" ");
        //递归打印左树
        preOrder(root.left);
        //递归打印右树
        preOrder(root.right);
    }
    // 中序遍历(左->右->根)
    void inOrder(TreeNode root){
        //判断当前根节点或子树头节点是否为空
        if(root==null)return;
        //先递归打印其左树
        inOrder(root.left);
        //打印根(此时左树已遍历完)
        System.out.print(root.val+" ");
        //递归打印其右树
        inOrder(root.right);
    }
    // 后序遍历(左->右->根)
    void postOrde(TreeNode root){
        //判断当前根节点或子树头节点是否为空
        if(root==null)return;
        //先递归打印其左树
        postOrde(root.left);
        //再递归打印其右树
        postOrde(root.right);
        //最后打印根节点
        System.out.print(root.val+" ");
    }

    //力扣上三种遍历的解法(遍历思路和子问题思路)

    //前序遍历(遍历思路)
    List<Character> list=new LinkedList<>();
    public List<Character> preTraver1(TreeNode root){
        if(root==null){
            return null;
        }
        list.add(root.val);
        preTraver1(root.left);
        preTraver1(root.right);
        return list;
    }
    //前序遍历(子问题思路)
    public List<Character> preTraver2(TreeNode root){
        //每一次递归都创建一个临时的链表来储存
        List<Character> ret=new LinkedList<>();
        if(root==null){
            return null;
        }
        ret.add(root.val);
        //将根节点的左树和右树都分别进行遍历然后将根节点和左树和右数进行拼接
        List<Character> leftTree=preTraver2(root.left);
        ret.addAll(leftTree);
        List<Character> rightTree=preTraver2(root.right);
        ret.addAll(rightTree);
        return ret;
    }


    //中序遍历(遍历思路)
    List<Character> list1=new LinkedList<>();
    public List<Character> inoderTraver1(TreeNode root){
        if(root==null)return null;
        inOrder(root.left);
        list1.add(root.val);
        inOrder(root.right);
        return list1;
    }
    //中序遍历(子问题思路)
    public List<Character> inoderTraver2(TreeNode root){
        List<Character> ret=new LinkedList<>();
        if(root==null)return ret;
        List<Character> leftTree=inoderTraver2(root.left);
        ret.addAll(leftTree);
        ret.add(root.val);
        List<Character> rightTree=inoderTraver2(root.right);
        ret.addAll(rightTree);
        return ret;
    }

    //后序遍历(遍历思路)
    List<Character> list3=new LinkedList<>();
    public List<Character> postTraver1(TreeNode root){
        if(root==null)return null;
        postTraver1(root.left);
        postTraver1(root.right);
        list3.add(root.val);
        return list3;
    }

    //后序遍历(子问题思路)
    public List<Character> postTraver2(TreeNode root){
        List<Character> ret=new LinkedList<>();
        if(root==null)return ret;
        List<Character> leftTree=postTraver2(root.left);
        ret.addAll(leftTree);
        List<Character> rightTree=postTraver2(root.right);
        ret.addAll(rightTree);
        ret.add(root.val);
        return ret;
    }


    // 获取树中节点的个数(子问题思路)
    int size(TreeNode root){
        if(root==null)return 0;
        return size(root.left)+size(root.right)+1;
    }
    //获取树的节点个数(遍历思路)
    int treeCount;
    public void size1(TreeNode root){
        if(root==null)return ;
        treeCount++;
        size1(root.left);
        size1(root.right);
    }


    // 获取叶子节点的个数(子问题思路)
    int getLeafNodeCount(TreeNode root){
        if(root==null)return 0;
        if(root.left==null&&root.right==null){
            return 1;
        }
        return  getLeafNodeCount(root.left)+getLeafNodeCount(root.right);
    }
    // 获取叶子节点的个数(遍历思路)
    int leafCount;
    public void getLeafNodeCount1(TreeNode root){
        if(root==null)return;
        if(root.left==null&&root.right==null){
            leafCount++;
        }
        getLeafNodeCount1(root.left);
        getLeafNodeCount1(root.right);
    }



    // 获取第K层节点的个数
    int getKLevelNodeCount(TreeNode root){
        return 0;
    }
    // 获取二叉树的高度
    int getHeight(TreeNode root){
       if(root==null)return 0;
       int leftH=getHeight(root.left);
       int rightH=getHeight(root.right);
       return Math.max(leftH,rightH)+1;
    }
    // 检测值为key的元素是否存在
    TreeNode find(TreeNode root, char key){
        if(root==null)return null;
        if(root.val==key){
            return root;
        }
        TreeNode leftKey=find(root.left,key);
        if(leftKey!=null)return leftKey;
        TreeNode rightKey=find(root.right,key);
        if(rightKey!=null)return rightKey;
        return null;
    }
    //层序遍历
    void levelOrder(){
        if(root==null)return;
        Queue<TreeNode>queue=new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            //弹出并打印队列顶的节点
            TreeNode top=queue.poll();
            System.out.print(top.val+" ");
            //判断该节点是否还有左右节点，有则入队列
            if(top.left!=null){
                queue.offer(top.left);
            }
            if(top.right!=null){
                queue.offer(top.right);
            }
        }
    }
    // 判断一棵树是不是完全二叉树
    boolean isCompleteTree(TreeNode root){
        List<Character> list=new LinkedList<>();
        return true;

    }
}
